Arbeitsbereich Datenbanken und Informationssysteme

Jahresbericht 1995 / 1996

Personal
Projekte
Kooperationen
Veröffentlichungen
Vorträge
Studienarbeiten

Personal

Professor

Güntzer, Ulrich, o. Prof., Dr. rer. nat.

Wissenschaftliche Angestellte

Argenton, Hans, Dipl.-Inform.
Becker, Peter, Dr. rer. nat.
Ludwig, Andreas, Dipl.-Inform. (seit Feb. 96)
Myka, Andreas, Dipl.-Inform.
Seipel, Dietmar, Prof., Dr. rer. nat. (bis Nov. 95)

Sekretariat und Technisches Personal

Weber, Monika, Fremdsprachensekretärin

Projekte

Deduktion unter Unsicherheit

Thema dieses Projekts ist der Umgang mit unsicherem Wissen. Untersucht werden Verfahren, die anwendbar sind, wenn subjektive oder unvollständige Information vorliegt. Der gewählte Ansatz geht von probabilistischen Methoden aus: Unsichere Regeln mit Wahrscheinlichkeits-Intervallen und explizite bedingte Unabhängigkeiten repräsentieren die probabilistische Information. Fixpunktberechnungsmethoden der Technologie der Deduktiven Datenbanken und neu entwickelte Subsumptions-Verfahren werden eingesetzt, um die komplexen Deduktionsprozesse zu beherrschen. Im Berichtszeitraum wurde das Projekt abgeschlossen, und die Resultate wurden in zwei ausführlichen Zeitschriftenartikeln und mehreren Kongreßbeiträgen veröffentlicht. Die im Projekt entwickelten Verfahren bilden die Grundlage des Systems Datalog-S , das beim Kooperationspartner Prof. Kießling zu einem vollständigen deduktiven Datenbanksystem ausgebaut wird.

Retrieval komplexer Objekte

Ziel dieses Projektes ist die Entwicklung von Techniken, die die schnelle, präzise und bequeme Suche in großen Baum- und Feature-Term-Datenbeständen ermöglichen. Am Beginn des Projektes stand die Untersuchung von Indexierungstechniken für Baumstrukturen; in der aktuellen Phase wird das Retrieval von gerichteten, azyklischen Graphen untersucht. Beide Strukturen sind essentiell für die Wissensrepräsentation u.a. in der Computerlinguistik. Als Anwendung wird in Zusammenarbeit mit dem Lehrstuhl für Ugaritische und Hebräische Sprach- und Literaturwissenschaft der Ludwig-Maximilians-Universität München Venona entwickelt, ein Retrievalsystem für Phrasenstruktur- und Feature-Bäume. Venona arbeitet momentan auf einer Datenbank von 120000 Morphosyntaxbäumen.

Darüberhinaus wurde an der Entwicklung von Anfragesprachen für das ad-hoc Retrieval von komplex strukturierten Objekten gearbeitet. Hierzu wurden dedizierte Sprachkonzepte entworfen und implementiert. Für die Spezifikation von Prädikaten auf Instanzen komplexer Objekte werden dabei Ansätze aus der temporalen Logik verwendet. Insbesondere wurde ein existierender Ansatz für das Retrieval von Listen auf Bäume und gerichtete azyklische Graphen erweitert.

Information-Broker

Es werden Software-Systeme (sog. Information-Broker ) untersucht, entworfen und entwickelt, die als Vermittler zwischen dem recherchierenden Endbenutzer und einer Vielzahl von verteilten und heterogenen Informationsdiensten mit Recherchemöglichkeit fungieren.

Ein Information-Broker weist einschlägige Informationsquellen nach und wählt, falls dies gefordert ist, auch diejenigen dieser Informationsquellen aus, die für die Recherche des Benutzers am geeignetsten erscheinen. Dazu muß Metainformation u.a. über die Anbieter von Informationsdiensten, über die Dienste selbst, ihre Kosten und über das Interessenprofil der Benutzer verwaltet, gesammelt und gepflegt werden.

Zentrale Dienstleistung des Information-Brokers ist es, einen einheitlichen Zugang zu einer Vielzahl von verteilten und heterogenen Informationsdiensten anzubieten. Die unterschiedlichen Protokolle, Zugangsprozeduren, Recherchesprachen, Formatkonventionen etc. werden vor dem Benutzer verborgen.

Der ANSI/NISO Z39.50 Protokollstandard gewinnt für bibliographische Anwendungen immer mehr an Bedeutung. Er legt detailliert fest, wie die Kommunikation zwischen einem Server, der bibliographische Daten zur Verfügung stellt, und einem Client abläuft, mit dem auf diesen Daten recherchiert werden soll. Unter anderem werden verschiedene Datenformate und Anfragesprachen definiert. Somit bietet Z39.50 (vor allem für den bibliographischen Bereich) einen Ausweg aus der heute vorhandenen Diversifikation und geringen Interoperabilität von Dienstanbietern und -nutzern. Dieser Protokollstandard muß daher beim Entwurf und bei der Implementierung eines Information-Brokers für recherchefähige Informationsdienste an zentraler Stelle berücksichtigt werden.

Die Mehrzahl der momentan verfügbaren bibliographischen Online-Datenbanken verfügt aber (noch) nicht über eine Z39.50-konforme Schnittstelle. Um dennoch viele dieser Datenbanken über Z39.50 ansprechen zu können, wurde eine Gateway-Software entwickelt, die für bibliographischen Online-Datenbanken, die über TELNET ansprechbar sind und über eine zeilenorientierte Benutzerschnittstelle verfügen, diese Z39.50-konforme Schnittstelle für den Benutzer bzw. Z39.50-Client transparent bereitstellt. Diese Gateway-Software kann Teil eines Information-Brokers sein, aber auch separat verwendet werden.

HyperFacs

Ziel des Projekts HyperFacs ist die weitgehend automatische Aufbereitung von Papierdokumenten in eine hypertextartig recherchierbare Form. Durch die Verwendung von Hypertextstrukturen werden Benutzer bzw. Leser von Dokumenten von der Aufgabe entbunden, ihr Informationsbedürfnis als Suchanfragen in einer Anfragesprache formulieren zu müssen. Stattdessen können sie im Dokumentenbestand assoziativ mit Hilfe sog. Links recherchieren. Im Vergleich zur Aufbereitung elektronischer ASCII-Dokumente ergeben sich vor allem zwei zusätzliche Aspekte, die zu berücksichtigen sind: Zum einen gehen die in einem Papierdokument "gespeicherten" Informationen weit über die reinen Zeichensequenzen hinaus. Zum anderen ist die Umwandlung derartiger non-coded information (auf Papier) in coded information stark fehlerbehaftet. Im Hinblick auf eine möglichst vollständige und fehlerfreie Erkennung von Links müssen beide Aspekte einfließen, um einen Benutzer bei seiner Informationssuche optimal zu unterstützen.

Optimierungsmethoden für Disjunktive Deduktive Datenbanken

Deduktive Datenbanken benutzen Konzepte der Logikprogrammierung für mächtige, deklarative Anfragesprachen und zur Verwaltung von großen Mengen von Daten. Neue Möglichkeiten für Wissensbanken erwachsen aus der Verwendung von unsicherem und unvollständigem Wissen , repräsentiert durch Logikprogramme mit disjunktiven Fakten und Regeln. Allerdings ist die Inferenz in disjunktiven deduktiven Datenbanken sehr aufwendig, besonders im Zusammenhang mit Negation.

Es wurden einige wichtige Auswertungsansätze theoretisch untersucht. Diese beruhen alle auf einer Reihe von grundlegenden Inferenztechniken: Hyperresolution , nicht-monotones Schließen mit Closed-World Annahmen und Negation-as-Failure-Konzepte. Diese Inferenztechniken wurden in einem System namens DISLOG mit Hilfe von neuen Datenstrukturen und effizienten Algorithmen implementiert.

Rechendienstleistungen im Internet / Verteiltes Modell-Management

Neue Netzwerktechnologien in Kombination mit dem INTERNET eröffnen heute die Möglichkeit, auf Daten oder Dienstleistungen in der ganzen Welt zuzugreifen. Während sich mit dem World Wide Web bereits eine Technologie für den einfachen Zugriff auf Dokumente im INTERNET etabliert hat, ist das Problem der Nutzung von Algorithmen und algorithmischem Metawissen noch nicht zufriedenstellend gelöst. Es stehen zwar Werkzeuge zum Anbieten von algorithmischen Dienstleistungen zur Verfügung, die einfache Kombination von Algorithmen, die Nutzung vorhandener Software, der Umgang mit komplex strukturierten Daten und die Repräsentation von Wissen zur Algorithmenauswahl werden von diesen aber nur bedingt unterstützt.

Im Vordergrund dieses Projekts steht die Fragestellung, wie Daten, algorithmische Dienstleistungen und algorithmisches Metawissen (insbesondere für diskrete Optimierungsprobleme) auf einfache Weise auf dem INTERNET angeboten und genutzt werden können. Hierzu wurden entsprechende Konzepte entwickelt und in dem System Progress implementiert. Basis von Progress sind eine shell-ähnliche und auf objekt-orientierten Konzepten beruhende Sprache zur Nutzung, sowie ein Serverprogramm zur Bereitstellung solcher Dienste.

Ein wesentliches Leistungsmerkmal sind dabei die vorhandenen Möglichkeiten zum Aufbau von Mehrwertdiensten. So gestatten Pläne eine Kombination von Algorithmen in Verbindung mit paralleler Ausführung. Mittels Modellen können Problemklassen in Form von abstrakten Datentypen zur Modellierung von Problemklassen auf dem INTERNET angeboten und genutzt werden. Weiterhin stehen Techniken für eine klassifikationsbasierte Methodenauswahl zur Verfügung.

MatSe - Verknüpfung mathematischer Server im Internet

Das INTERNET bietet in zunehmendem Maße Möglichkeiten des Zugriffs auf entfernt installierte Software. Eine neue Generation von WWW-Browsern (HotJava, Netscape) stellt Möglichkeiten bereit, Programme in Form von sogenannten Java-Applets auf den lokalen Rechner zu laden und durch eine im Browser integrierte virtuelle Maschine ausführen zu lassen. Für rechenintensive Anwendungen sind solche client-side basierten Ansätze aber nur bedingt geeignet. So sind für harte Optimierungsprobleme server-side basierte Ansätze geeigneter, da für deren effiziente Lösung sehr leistungsstarke Rechner in Verbindung mit wissenschaftlicher Spezialsoftware notwendig sind. Client-side basierte Ansätze können in diesem Zusammenhang für die Unterstützung bei der Problemformulierung und für die Präsentation der Ergebnisse eingesetzt werden.

Das Projekt MatSe (Verknüpfung Mat hematischer Se rver im INTERNET) soll die oben genannten Technologien einsetzen, um mathematische Forschung, die sich mit der Entwicklung effizienter Algorithmen beschäftigt, auf neuartige Weise zu unterstützen. Für einen Verbund von vier Forschergruppen der mathematischen Optimierung und des Operations Research an Hochschulen in Berlin, Karlsruhe, Kiel, und Osnabrück wird eine Infrastruktur zur wissenschaftlichen Kooperation über Weitverkehrsnetze zur Verfügung gestellt. Im Vordergrund steht dabei die gegenseitige Nutzung von wissenschaftlicher Software (insbesondere Spezialalgorithmen) zur Lösung komplexer Optimierungsprobleme aus dem Bereich der Terminplanung (Scheduling). Für die server-side basierte Bereitstellung von Algorithmen werden dabei die bei den Projektpartnern entwickelten Systeme MMM (HU Berlin) und Progress (Universität Tübingen) eingesetzt.

Kooperationen

Veröffentlichungen

  1. H. Argenton and P. Becker. Efficient Retrieval of Labeled Binary Trees. IEICE Transactions on Information and Systems, Special Issue on Advanced Database Technologies , E78-D(11):1433-1438, 1995.

  2. P. Becker. A Framework for Providing and Using Algorithms and Algorithmic Meta Knowledge on the INTERNET. In S. Ram and M. Jarke, editors, Proceedings of the 5th Annual Workshop on Information Technologies & Systems (WITS'95) , number 95-15 in Aachener Informatik-Berichte, pages 2-11, 1995.

  3. P. Becker. A Temporal Logic Based Approach for Querying Lists, Trees, and DAGs in Databases. In N. Revell and A. M. Tjoa, editors, Proceedings of the 6th International Conference on Database and Expert Systems Applications (DEXA'95) , volume 978 of Lecture Notes in Computer Science , pages 293-302. Springer, 1995.

  4. P. Becker. A Temporal Logic Based Approach for Querying Lists, Trees, and DAGs in Databases. Technical Report WSI-95-1, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen, 1995.

  5. P. Becker. An Embeddable and Extendable Language for large-scale Programming on the INTERNET. Technical Report WSI-95-7, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen,

  6. P. Becker. Eine Anfragesprache für das Retrieval von Listen, Bäumen und DAGs in Datenbanken. In C. Eckert, H.-J. Klein, and T. Polle, editors, Proceedings 7. Workshop Grundlagen von Datenbanken , number 12/95 in Hildesheimer Informatik-Berichte, pages 15-19. Universität Hildesheim, 1995.

  7. P. Becker. An Embeddable and Extendable Language for large-scale Programming on the INTERNET. In Proceedings of the 16th International Conference on Distributed Computing Systems (ICDCS'96)

  8. P. Becker. Verteiltes Modell-Management und Objektbanken für diskrete Probleme und diskrete Strukturen . PhD thesis, Wilhelm-Schickard-Institut für Informatik, Universität Tübingen,

  9. H. Decker, U. Geske, T. Kakas, C. Sakama, D. Seipel, and T. Urpi, editors. Proceedings of the "Workshop on Deductive Databases and Logic Programming - Abduction in Deductive Databases and Knowledge-based Systems", Shonan Village Center, Japan GMD-Studien Nr. 266, ISBN 3-88457-266-0, 1995.

  10. G. Köstler, W. Kießling, H. Thöne, and U. Güntzer. Fixpoint Iteration with Subsumption in Deductive Databases. Journal of Intelligent Information Systems 4 , pages 123-148, 1995.

  11. T. Lukasiewicz, W. Kießling, G. Köstler, and U. Güntzer. Taxonomic and Uncertainty Constraints in Object-Oriented Databases - the TOP-Approach. In Proceedings of the 1995 ACM CIKM International Conference on Information and Knowledge Management, Baltimore, USA , pages 241-249. ACM Press, 1995.

  12. A. Myka. Automatische Generierung von Hypertexten. In E. Neugebauer and S. Wiesener, editors, Report 7. Workshop Hypermedia & KI, 16.-17. November, 1995, Hannover, FR-1996-001 , pages 7-9, 1996.

  13. A. Myka, H. Argenton, and U. Güntzer. Towards Automatic Hypertextual Representation of Linear Texts. Technical Report 96-12, Wilhelm-Schickard-Institut, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, 1996.

  14. A. Myka, H. Argenton, and U. Güntzer. Towards Automatic Hypertextual Representation of Linear Texts. In Proceedings of the 3rd Internat. Workshop on Principles of Document Processing (PODP' 96), September 23, 1996, Palo Alto, California, USA , LNCS, (to appear).

  15. A. Myka and U. Güntzer. Automatic Hypertext Conversion of Paper Document Collections. In N. Adam, B. Bhargava, and Y. Yesha, editors, Advances in Digital Libraries , number 916 in LNCS, pages 65-90. Springer-Verlag, 1995.

  16. A. Myka and U. Güntzer. HyperFacs - Building and Using a Digitized Paper Library. SIGLINK Newsletter, Special Issue on Digital Libraries pages 4-6, September 1995.

  17. A. Myka and U. Güntzer. Fuzzy Full-Text Searches in OCR Databases. In N. Adam, B. Bhargava, M. Halem, and Y. Yesha, editors, Digital Libraries , number 1082 in LNCS, pages 131-145. Springer-Verlag, 1996.

  18. A. Myka and U. Güntzer. Processing Hypertext Link Descriptions. In Proceedings of the Internat. Symposium on Cooperative Database Systems for Advanced Applications (CODAS'96), December 5-7, 1996, Kyoto, Japan pages 204-211, 1996.

  19. D. Seipel. Efficient Reasoning in Disjunctive Deductive Databases. Habilitationsschrift, Wilhelm-Schickard-Institut, Universität Tübingen, Sand 13, D-72076 Tübingen, Germany, 1995.

  20. D. Seipel. Reasoning with Integrity Constraints in Disjunctive Deductive Databases. In Proc. Workshop on "Semantics in Databases" at ICDT'95, Prague, Czech Republic

  21. D. Seipel and U. Güntzer. Mixed Fixpoint Theory for Disjunctive Deductive Databases. In Proc. Eleventh Workshop on Logic Programming 1995 (WLP'95) , pages 227-236, 1995.

  22. D. Seipel, J. Minker, and C. Ruiz. Model Generation and State Generation for Disjunctive Logic Programs. Technical Report CS-TR-3546, UMIACS-TR-95-99, Dept. of Computer Science and Institute for Advanced Computer Studies, Univ. of Maryland, College Park, USA, 1995.

  23. H. Thöne, U. Güntzer, and W. Kießling. Modelling, Chaining and Fusion of Uncertain Knowledge. In Ling. T.W. and Y. Masunaga, editors, Proceedings 4th International Conference on Database Systems for Advanced Applications, Singapore , pages 197-205. World Scientific Publishing Company, 1995.

  24. H. Thöne, W. Kießling, and U. Güntzer. Increased Robustness of Bayesian Networks through Probability Intervals. J. Approximate Reasoning , (to appear).

Vorträge

  1. Peter Becker, 27.4.95, Humboldt-Universität zu Berlin, Modellbanksysteme und "Programming in the Large"

  2. Andreas Myka, 16.5.95, ADL'95, Forum on Research & Technology Advances in Digital Libraries, McLean, Virginia, USA, Fuzzy Full-Text Searches in OCR Databases

  3. Dietmar Seipel, 18.8.95, University of Maryland, College Park, USA, The DISLOG-System

  4. Dietmar Seipel, 5.9.95, University of Maryland, College Park, USA, Minimal Model Reasoning and its Efficient Implementation

  5. Peter Becker, 7.9.95, DEXA'95, Conference on Database and Expert Systems Applications, London, United Kingdom, A Temporal Logic Based Approach for Querying Lists, Trees, and DAGs in Databases

  6. Peter Becker, 13.9.95, SOR'95, Symposium on Operations Research, Passau, A Framework for Providing and Combining Executable Optimization Algorithms via the INTERNET

  7. Dietmar Seipel, 29.9.95, 11th Workshop on Logic Programming WLP'95, Technische Universit\ät Wien, Österreich, Mixed Fixpoint Theory for Disjunctive Deductive Databases

  8. Hans Argenton, 6.10.95, Symposium Syntaktische Probleme des Althebräischen, LMU München, Venona - Ein Retrievalsystem für annotierte Syntaxbäume

  9. Andreas Myka, 16.11.95, 7. Workshop "Hypermedia und KI", Hannover, Automatische Generierung von Hypertexten

  10. Dietmar Seipel, 28.11.95, Ludwig-Maximilians-Universit\ät M\ünchen, Modell- und State-Generierung in disjunktiven deduktiven Datenbanken

  11. Peter Becker, 9.12.95, WITS'95, Workshop on Information Technologies and Systems, Amsterdam, Netherlands, A Framework for Providing and Using Algorithms and Algorithmic Meta Knowledge on the INTERNET

  12. Peter Becker, 10.1.96, Humboldt-Universität zu Berlin, Anbieten und Nutzen von Algorithmentechnologie im INTERNET

  13. Peter Becker, 14.2.96, Promotionskolloquium der Fakultät für Informatik, Universität Tübingen, Verteiltes Modell-Management und Objektbanken für diskrete Probleme und diskrete Strukturen

  14. Ulrich Güntzer, 27.2.96, Dagstuhl Workshop On Networked Information Systems Discovery, Retrieval and Dissemination, A Framework For Providing And Using Algorithms And Algorithmic Meta Knowledge On The Internet

  15. Peter Becker, 30.5.96, ICDCS'96, Conference on Distributed Computing Systems, Hongkong, An Embeddable and Extendable Language for large-scale Programming on the INTERNET

  16. Peter Becker, 5.6.96, DFG-Workshop über "Projektplanung mit beschränkten Ressourcen", Karlsruhe, Mathematische Server im Internet - das Projekt MatSe -

  17. Peter Becker, 6.9.96, SOR'96, Symposium on Operations Research, Braunschweig, Distributed and Interoperable Mathematical Objects and Services

  18. Andreas Myka, 23.9.96, Workshop on Principles of Document Processing (PODP'96), Palo Alto, California, USA, Towards Automatic Hypertextual Representation of Linear Texts

  19. Andreas Myka, 6.12.96, International Symposium on Cooperative Database Systems for Advanced Applications (CODAS'96), Kyoto, Japan, Processing Hypertext Link Descriptions

Studienarbeiten

  1. Aicher, Lutz, Vollständig expandierte Baumgramm-Indexe, 1996

  2. Andresen, Nikolaus, WWW-Schnittstellen zu Datenbanken, 1996

  3. Blaurock, Markus, Indexstrukturen für Baum-Datenbanken, 1995

  4. Haidt, Markus, Ranking und Unranking von B-Bäumen, 1996

  5. Marandiuc, Laura, Entwicklung eines flexiblen Sicherheitskonzepts für DBMS am Beispiel der Firma transtec AG, 1995

  6. Scheffczyk, Peter, Implementierung der Fixpunktberechnung des TPS-Operators für disjunktive Logikprogramme in C++, 1995

  7. Schimkat, Ralf-Dieter, Dynamische Konversion von HyperMan-Datenbanken nach HTML, 1996

  8. Schreiner, Jörg, Ein Werkzeug zum automatischen Testen von DISLOG-Operatoren, 1995

  9. Volland, Alexandra, Fuzzy-Volltext-Retrieval in OCR-Datenbanken, 1996

  10. Wastl, Ralf, Stratifizierung von disjunktiven normalen Logikprogrammen und Berechnung perfekter Modelle, 1995

  11. Wiedmann, Jochen, Datenbankorientierte Erweiterung des Methodenbanksystems M, 1995

  12. Zhao, Dongyan, Realisierung einer WWW-Schnittstelle zum System Progress, 1996